package listbyorder.access101_200.test139;

import java.util.HashMap;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/11 11:35
 */
public class Solution1 {

    public boolean wordBreak(String s, List<String> wordDict) {
        // 首先遍历一下字符串列表，找到最大的长度和最小的长度
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (String word : wordDict) {
            min = Math.min(min, word.length());
            max = Math.max(max, word.length());
        }
        if (s.length() < min) return false;
        HashMap<Integer, Boolean> memo = new HashMap<>();
        return dfs(s, wordDict, min, max, 0, s.length(), memo);
    }

    private boolean dfs(String s, List<String> wordDict, int min, int max, int c, int len, HashMap<Integer, Boolean> memo) {
        if (c == len) return true;
        if (memo.containsKey(c)) {
            return memo.get(c);
        }
        for (int i = min; i <= max && c + i <= len; i++) {
            if (wordDict.contains(s.substring(c, c + i)) && dfs(s, wordDict, min, max, c + i, len, memo)) {
                memo.put(c, true);
                return true;
            }
        }
        memo.put(c, false);
        return false;
    }
}
